package oj;

public class Day46F {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length==0) return 0;
        int times=1;
        int result=array[0];

        for(int i=1;i<array.length;i++){
            if(times!=0){
                if(array[i]!=result){
                    times--;
                }else{
                    times++;
                }
            }else{
                result=array[i];
                times=1;
            }
        }
        times=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==result) times++;
        }
        return (times>array.length/2)?result:0;
    }
}
